package leetcode;

public class ContainerOfWater {

	public static void main(String[] args) {
		int[] height = {6, 5, 4, 3, 2, 1};
		int[] height1 = {200,199,198,197,196,195,194,193,192,191,190,1};
//		int res = maxArea(height);
//		System.out.println(res);
//		
//		for (int i = 0; i < 10; i++) {
//			int[] array = generateRandomArray();
//			int result = maxArea(array);
//			for (int j : array) {
//				System.out.print(" " + j);
//			}
//			System.out.println();
//			System.out.println(result);
//		}
		
		ContainerOfWater object = new ContainerOfWater();
		System.out.println(object.maxArea2(height1));
	}
	
	//生成随机的数组，数组的数字也是随机生成的
	public static int[] generateRandomArray() {
		int[] arr = new int[(int) (Math.random() * 98) + 2];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = (int) (Math.random() * 200) + 2;
		}
		return arr;
	}
	
	//这个不是用来做leetcode上的那道题的
	//这个是柱形，而leetcode上面的是线，所以不一样
	public static int maxArea(int[] height) {
		if (height == null || height.length <= 3) {
			return -1;
		}
		// set two pointer
		int leftMax = height[0]; // record the left max value
		int rightMax = height[height.length - 1]; // record the right max value
		int left = 1; // left pointer
		int right = height.length - 2; // right pointer
		int value = 0;
		while (left <= right) {
			// leftMax is the 瓶颈
			if (leftMax <= rightMax) {
				value += Math.max(0, leftMax - height[left]); // attention,
																// leftMax -
																// height[left]
																// it might less
																// than 0
				leftMax = Math.max(leftMax, height[left++]);
			} else {
				value += Math.max(0, rightMax - height[right]);
				rightMax = Math.max(rightMax, height[right--]);
			}
		}
		return value;
	}
	
	
	public int maxArea2(int[] height) {
		if (height == null || height.length <= 1) {
			return -1;
		}
		// set two pointer
		int left = 0;	// left pointer
		int right = height.length - 1;	// right pointer
		int maxArea = 0;
		while (left <= right) {
			maxArea = Math.max(maxArea, (right - left) * Math.min(height[left], height[right]));
			// left is the 瓶颈, 无论怎么向右移动right都无法得到比当前面积更大的了
			if (height[left] <= height[right]) {
				left++;
			} else {
			    //rightMax 是瓶颈
				right--;
			}
		}
		return maxArea;
	}
}
